package org.liaohailong.helloworld.practice;

/**
 * Author: liaohailong
 * Date: 2021/6/13
 * Time: 22:50
 * Description: 初级算法 - 动态规划
 **/
public class DPPractice {
    // LC 爬楼梯
    public int climbStairs(int n) {
        return (int) ((Math.pow((1 + Math.sqrt(5)) / 2, n + 1) - Math.pow((1 - Math.sqrt(5)) / 2, n + 1)) / Math.sqrt(5));
    }

    // LC 买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        if (prices.length < 1) return 0;
        int min = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            maxProfit = Math.max(prices[i] - min, maxProfit);
        }
        return maxProfit;
    }

    //    输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
    //    输出：6
    //    解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
    // LC 最大子序和
//    public int maxSubArray(int[] nums) {
//        int N = nums.length;
//        int[][] dp = new int[N][N];
//        // 初始化length为1的值
//        for (int i = 0; i < N; i++) {
//            dp[i][i] = nums[i];
//        }
//        // dp[i,j] = dp[i,j-1] + dp[j,j];
//        // if i == j -> dp[i,j] = arr[i];
//        // 从左往右，从下往上
//        // i = start point
//        // j = end point
//        int maxVal = Integer.MIN_VALUE;
//        for (int j = 0; j < N; j++) {
//            for (int i = j; i >= 0; i--) {
//                int val = _maxSubArray(nums, i, j, dp);
//                dp[i][j] = val;
//                if (val > maxVal) maxVal = val;
//            }
//        }
//        return maxVal;
//    }
//
//    private int _maxSubArray(int[] nums, int i, int j, int[][] dp) {
//        if (dp[i][j] != 0) return dp[i][j];
//        if (j > i) {
//            return _maxSubArray(nums, i, j - 1, dp) + nums[j];
//        } else {
//            return nums[i];
//        }
//    }


    // LC 最大子序和
    public int maxSubArray(int[] nums) {
//        int N = nums.length;
//        int[] dp = new int[N];
//        dp[0] = nums[0];
//        int max = nums[0];
//        for (int i = 1; i < N; i++) {
//            dp[i] = Math.max(dp[i - 1], 0) + nums[i];
//            max = Math.max(max, dp[i]);
//        }
//        return max;

        int N = nums.length;
        int curr = nums[0];
        int max = curr;
        for (int i = 1; i < N; i++) {
            curr = Math.max(curr, 0) + nums[i];
            max = Math.max(curr, max);
        }
        return max;
    }

    // LC 打家劫舍
    public int rob(int[] nums) {
        if (nums.length < 1) return 0;
        if (nums.length < 2) return nums[0];
        if (nums.length < 3) return Math.max(nums[0], nums[1]);

        int dp0 = nums[0]; // 偷到第0家，最大值
        int dp1 = Math.max(nums[1], nums[0]);// 偷到第1家，最大值
        int max = dp1;
        for (int i = 2; i < nums.length; i++) {
            // 今天偷和不透做比较，取一个最大值
            // dp[i] 始终都是第i天最大收益
            int temp = dp1;
            dp1 = Math.max(nums[i] + dp0, dp1);
            dp0 = temp;
            max = Math.max(dp1, max);
        }

        return max;
    }

}
